/* 以下概念介绍引自 https://blog.csdn.net/weixin_38984030/article/details/86076074 */
/*
    双链表 概念
    单链表节点的缺点是只有一个后继节点，访问前驱节点只能从头遍历（如插入、删除），时间复杂度为O(n)。
    而双链表，即添加一个指向前驱的节点。
    
    基本功能：增、删、改、查、判（判空，判满）、排（排序）、复（复位）
    
    双链表的查找和单链表的相同，双链表的构造也分为头插和尾插，与单链表唯一不同的是修改前驱指针prior，
    插入和删除时不同，因为需要修改两个指针，如果给定要操作的节点，插入和删除的时间复杂度为O(1)。
    
    ll 表示 linked list（链表）
*/

/* 双链表的节点基本结构如下 */
struct simple_ll_struct
{
    int data;
    struct simple_ll_struct *prior, *next;
}

/* 有关于基本操作的步骤，画画图更好理解，梳理出来并不算难 */

/* 插入节点：在p节点后插入s节点，先断后连，先把p和原后继节点的链条给断了，使后继节点只跟s节点有关 
    ① s.next = p.next; // 先断了p的后继
    ② p.next.prior = s; // 在断了p后继的前驱
    ③ s.prior = p; // 让s的前驱指向p
    ④ p.next = s; // p的后继指向s，重新连接上链条，此步必须在①②之后
*/

/* 删除节点：删除节点p的后继节点q，也是先断后连，把q和其后继节点的关系，转让给p即可
    ①p.next = q.next; // 先断了q的后继
    ②q.next.prior = p; // 在断了q后继的前驱
     
    删除节点q的前驱节点p，把p和去前驱节点的关系转让给q即可：
    ①q = p.prior.next; // 把p前驱节点的后继改成q
    ②q.prior = p.prior; // 把q的前驱节点改成p的前驱节点
*/


/*
    一个用 宏 实现的双链表，很实用
    https://mp.weixin.qq.com/s/q31_MlmHH7pgYdQqI5q6KQ
*/

